There are many ways to construct a computer model of a physical structure, such as by scanning the structure and generating a virtual model from the resultant scan data. These techniques become more complicated for large structures, such as a manufacturing facility or a petroleum refinery, which can have very complex surfaces due to the amount of piping, machinery, and other apparatus that would be present in the scan.
One technique for constructing these computer models begins by laser scanning the structure. In the laser scanning process, a laser beam scans across a view that encompasses the structure of interest. The scanning device measures a large number of points that lie on surfaces within an unobstructed line of sight of the scanning device. Each scan point has a measured location in 3D space, to within some measurement error, that typically is recorded relative to a point (x,y,z) in the local coordinate system of the scanner. The resulting collection of points is often referred to as one or more point clouds, where each point cloud can include points that lie on many different surfaces in the scanned view. For example, a scan taken at a petroleum refinery may include a point cloud that has points that correspond to pipes, elbows, valves, pumps, and structural steel members.
Once the 3D data for the points in the scan have been collected, the data typically are processed to generate a computer (virtual) model of the structure. One technique for processing the 3D point data is to group together points that lie on the same surface. The grouped points then are processed with a prior-art fit procedure that defines a surface consistent with the points. For example, the points that lie on the surface of a cylindrical storage tank can be grouped together, then processed by a prior-art fit procedure to construct a geometric model of the surface of the cylindrical tank.
One technique for grouping together the points that lie on the same surface, known as manual segmentation or point cloud partitioning, is to manually partition the points that appear to lie on the surface of interest into a group. For example, a user can select one or more groups of points and then draw a polygonal fence around the points that appear to lie on the surface of interest, while excluding points that lie on other surfaces. Once the fence is created and a group of points of interest is defined, the grouping process may need to be repeated to remove spurious points that do not lie on the desired surface. Since the view presented to the user is a 2D projection of 3D space, points that appear to be on the same surface in a 2D view may actually be on different surfaces. The user must then analyze the same scene from another view and manually partition the points that appear to lie on the surface of interest. The user typically can isolate points on the desired surface in one or two manual segmentation steps, but in some cases additional segmentation may be needed.
A fit procedure then is utilized to generate a geometric primitive of the surface of interest from the selected surface points. Once the primitive has been generated, fit statistics are reviewed. Frequently, the fit statistics fall below acceptable levels due to the inadvertent inclusion of points not on the surface of interest. When this occurs, the user must perform additional manual segmentation steps to remove these spurious points. As a result, this procedure for generating a computer model of a surface from 3D point data is a time-consuming and error-prone process.
In another prior art process, described in U.S. Pat. No. 6,771,840, entitled “APPARATUS AND METHOD FOR IDENTIFYING THE POINTS THAT LIE ON A SURFACE OF INTEREST,” filed May 18, 2000, hereby incorporated by reference herein, points that lie on a surface of interest can be identified without need for the user to manually partition the points. Instead, the user can select at least one seed point that lies on the surface of interest. Points in vicinities of the seed points that are likely to lie on the same surfaces as the seed points can be added. The system considers a number of neighboring points, and identifies points to be added on the basis of a uniformity of spacing, using a predetermined spacing factor.
These points then undergo a fitting procedure to define a surface type, as well as a candidate surface. After the candidate surface has been defined, a second set of points is defined that includes the seed points. To the second set of points are added the points that are within a predetermined distance of the candidate surface. Following this, the second set of points is partitioned into groups of contiguous points and the candidate surface is redefined with the surface type and the groups of contiguous points that include the seed points. Once the second set of points has been partitioned into subgroups, a shrinking procedure is applied to each subgroup to remove boundary points. The candidate surface then is redefined using only subgroups that include the seed points. This process of partitioning and/or redefining can be iterated a predetermined number of times (as specified by the user) or until some convergence criteria is satisfied.
Problems with such an approach occur for many objects, where a surface of that object (such as piping in a factory) might span multiple geometric objects, including runs of straight, cylindrical pipe, connected by elbow and/or flange regions. A single geometric model as used in the prior art cannot be used to cover all the possible shapes and configurations of such an object. It would be necessary to separately model each portion of the object. This can be somewhat difficult, as point-by-point, grow-from-seed methods do not lend themselves to convenient user intervention.
Another problem arises with unordered data. Many prior art methods such as grow-from-seed methods or cluster-and-merge methods assume that data are collected from a single viewpoint and are properly ordered, such as in scanlines or in a 2D grid. This information is relied upon for estimating surface normals and identifying discontinuities. Problems arise, however, in situations such as where data are merged from multiple viewpoints and/or registered from multiple scans over the same portions of a surface. Typical orderings, such as scanlines and 2-D grids, may not be always applicable to data generated using methods such as GPS. In general, 3D points measured from different points of view may not have a clean 2D topology, due to factors such as measurement noise and point overlap. This can lead to data that never meet fit criteria or that provide incorrect results. Further, grid and scanline based methods, as well as methods based on merging adjacent regions having similar properties, are sensitive to occlusions, particularly “shadows” cast by other objects in the scene.
Another problem with these existing approaches is that point-by-point methods are forced to use full data density, even if not required by the application. There is no inherent sense of scale to guide point decimation. Derivative methods, including local curvature methods and methods depending on normal vectors, tend to degrade as the point spacing becomes small relative to the measurement noise in the data. Further, many existing algorithms require an estimate of the surface normal vector at each data point, which can be computationally intensive (especially on unordered data) and sensitive to point density, noise, and occlusions. While most of these methods can be applied to a subset of data points, there is no mechanism for using subset results to indicate which parts of the remaining data are likely to include continuations of the surface found. This leads to inefficient modeling of smaller portions of dense and/or large databases.